from time import time
from random import randint

def cmp(x,y):
    return y-x;

def merge_sort(a):
    if len(a)<2 :
        return a;
    h = len(a)/2;
    l = merge_sort(a[:h])
    r = merge_sort(a[h:])
    res = []
    i = j = 0
    while i<len(l) and j<len(r) :
        if l[i]<=r[j] :
            res.append(l[i])
            i += 1
        else :
            res.append(r[j])
            j += 1
    # res += l if i<len(l) else r
    if i<len(l) :
        while i<len(l) :
            res.append(l[i])
            i += 1
    else :
        while j<len(r) :
            res.append(r[j])
            j += 1
    return res

def main():
    n = int(input())
    data = [randint(0,n*n) for i in xrange(n)]
    # print data
    print 'merge sort begin:'
    print ' running...'
    t1 = int(time()*1000)
    res = merge_sort(data)
    t2 = int(time()*1000)
    # print res
    print 'merge sort end.'
    print 'run time: %dms'%(t2-t1)
    p = True
    for i in xrange(n-1) :
        if res[i]>res[i+1] :
            p = False
            break
    print 'the answer is '+('right'if p else'wrong')+' !!!'




if __name__ == '__main__' :
    main()
